lib/Mi manual de algoritmos/version_world_finals_2009/src/grafos/bellman.cpp

   1 //Complejidad: O(V*E)
   2
   3 const int oo = 1000000000;
   4 struct edge{
   5   int v, w; edge(){} edge(int v, int w) : v(v), w(w) {}
   6 };
   7 vector<edge> g[MAXNODES];
   8
   9 int d[MAXNODES];
  10 int p[MAXNODES];
  11 // Retorna falso si hay un ciclo de costo negativo alcanzable
  12 // desde s.  Si retorna verdadero, entonces d[i] contiene la
  13 // distancia más corta para ir de s a i.  Si se quiere
  14 // determinar la existencia de un costo negativo que no
  15 // necesariamente sea alcanzable desde s, se crea un nuevo
  16 // nodo A y nuevo nodo B. Para todo nodo original u se crean
  17 // las aristas dirigidas (A, u) con peso 1 y (u, B) con peso
  18 // 1. Luego se corre el algoritmo de Bellman-Ford iniciando en
  19 // A.
  20 bool bellman(int s, int n){
  21   for (int i=0; i<n; ++i){
  22     d[i] = oo;
  23     p[i] = -1;
  24   }
  25
  26   d[s] = 0;
  27   for (int i=0, changed = true; i<n-1 && changed; ++i){
  28     changed = false;
  29     for (int u=0; u<n; ++u){
  30       for (int k=0; k<g[u].size(); ++k){
  31         int v = g[u][k].v, w = g[u][k].w;
  32         if (d[u] + w < d[v]){
  33           d[v] = d[u] + w;
  34           p[v] = u;
  35           changed = true;
  36         }
  37       }
  38     }
  39   }
  40
  41   for (int u=0; u<n; ++u){
  42     for (int k=0; k<g[u].size(); ++k){
  43       int v = g[u][k].v, w = g[u][k].w;
  44       if (d[u] + w < d[v]){
  45         //Negative weight cycle!
  46
  47         //Finding the actual negative cycle. If not needed
  48         //return false immediately.
  49         vector<bool> seen(n, false);
  50         deque<int> cycle;
  51         int cur = v;
  52         for (; !seen[cur]; cur = p[cur]){
  53           seen[cur] = true;
  54           cycle.push_front(cur);
  55         }
  56         cycle.push_front(cur);
  57         //there's a negative cycle that goes from
  58         //cycle.front() until it reaches itself again
  59         printf("Negative weight cycle reachable from s:\n");
  60         int i = 0;
  61         do{
  62           printf("%d ", cycle[i]);
  63           i++;
  64         }while(cycle[i] != cycle[0]);
  65         printf("\n");
  66         // Negative weight cycle found
  67
  68         return false;
  69       }
  70     }
  71   }
  72   return true;
  73 }